P2178 [NOI2015] 品酒大会

字符串的贡献在第一个位置，为了与 $\text{endpos}$ 对应上考虑将串翻转。

两杯酒 $p,q$ 的最大相似度就是 $\text{lcp}(p,q)$ ，即后缀自动机 $\text{parent}$ 树上 $last_p,last_q$ 两个节点的 $\text{lca}$。

大的相似度会对较小的相似度产生影响，可以看作在后缀树上从深度大的节点考虑。

第一问维护子树包含叶子数量 ($|endpos|$) , 因为每个节点是长度连续的子串，在差分数组上修改即可。

第二问维护子树最大/小值，还有次大/小值，这样乘积的最大值便为最大次大的乘积与最小次小乘积的 max。只需要修改最长串即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long

#define Mx 0x3f3f3f3f
#define Mn -0x3f3f3f3f

const int MAXN = 3e5;
int a[ MAXN + 5 ];

LL Ans1[ MAXN + 5 ] , Ans2[ MAXN + 5 ];
struct Suffix_Automaton {
    int rt , siz , last;
    int trs[ 2 * MAXN + 5 ][ 26 ] , fail[ 2 * MAXN + 5 ];
    int mxlen[ 2 * MAXN + 5 ] , endpos[ 2 * MAXN + 5 ];

	Suffix_Automaton( ) {
        rt = siz = last = 1;
        for( int i = 0 ; i <= 1 ; i ++ ) for( int j = 1 ; j <= 2 * MAXN ; j ++ ) mx[ i ][ j ] = Mn , mn[ i ][ j ] = Mx;
    }
    
	void Extend( int chr ) {
        int nw = ++ siz , u = last;
        mxlen[ nw ] = mxlen[ u ] + 1;
        for( ; u && !trs[ u ][ chr ] ; u = fail[ u ] ) trs[ u ][ chr ] = nw;
        if( !u ) fail[ nw ] = 1;
        else {
            int v = trs[ u ][ chr ];
            if( mxlen[ v ] == mxlen[ u ] + 1 ) fail[ nw ] = v; 
            else {
                int w = ++ siz; mxlen[ w ] = mxlen[ u ] + 1; fail[ w ] = fail[ v ];
                for( int i = 0 ; i < 26 ; i ++ ) trs[ w ][ i ] = trs[ v ][ i ];
                fail[ v ] = fail[ nw ] = w;
                for( ; u && trs[ u ][ chr ] == v ; u = fail[ u ] ) trs[ u ][ chr ] = w;
            }
        }
        last = nw; endpos[ last ] = 1;
    }
	void Build( int len , char *str ) {
		for( int i = 1 ; i <= len ; i ++ ) {
            Extend( str[ i ] - 'a' );
            mx[ 0 ][ last ] = mn[ 0 ][ last ] = a[ i ];
        }
	}
    
    int buc[ MAXN + 5 ] , tp[ 2 * MAXN + 5 ];
    void Sort( ) {
        for( int i = 1 ; i <= siz ; i ++ ) buc[ mxlen[ i ] ] ++;
        for( int i = 1 ; i <= MAXN ; i ++ ) buc[ i ] += buc[ i - 1 ];
        for( int i = siz ; i >= 1 ; i -- ) tp[ buc[ mxlen[ i ] ] -- ] = i;
    }

    int mx[ 2 ][ 2 * MAXN + 5 ] , mn[ 2 ][ 2 * MAXN + 5 ];
    void Solve() {
        Sort();
        for( int i = siz ; i >= 1 ; i -- ) {
            int u = tp[ i ] , fa = fail[ u ];
            endpos[ fa ] += endpos[ u ];
            
            if( mx[ 0 ][ u ] > mx[ 0 ][ fa ] ) mx[ 1 ][ fa ] = mx[ 0 ][ fa ] , mx[ 0 ][ fa ] = mx[ 0 ][ u ];
            else if( mx[ 0 ][ u ] > mx[ 1 ][ fa ] ) mx[ 1 ][ fa ] = mx[ 0 ][ u ];
            if( mx[ 1 ][ u ] > mx[ 1 ][ fa ] ) mx[ 1 ][ fa ] = mx[ 1 ][ u ];
            
            if( mn[ 0 ][ u ] < mn[ 0 ][ fa ] ) mn[ 1 ][ fa ] = mn[ 0 ][ fa ] , mn[ 0 ][ fa ] = mn[ 0 ][ u ];
            else if( mn[ 0 ][ u ] < mn[ 1 ][ fa ] ) mn[ 1 ][ fa ] = mn[ 0 ][ u ];
            if( mn[ 1 ][ u ] < mn[ 1 ][ fa ] ) mn[ 1 ][ fa ] = mn[ 1 ][ u ];

            Ans1[ mxlen[ fa ] + 1 ] += 1ll * endpos[ u ] * ( endpos[ u ] - 1 ) / 2;
            Ans1[ mxlen[ u ] + 1 ] -= 1ll * endpos[ u ] * ( endpos[ u ] - 1 ) / 2;
            if( endpos[ u ] != 1 )
                Ans2[ mxlen[ u ] ] = max( Ans2[ mxlen[ u ] ] , max( 1ll * mx[ 0 ][ u ] * mx[ 1 ][ u ] , 1ll * mn[ 0 ][ u ] * mn[ 1 ][ u ] ) );
        }
    }
}SAM;

int n; char str[ MAXN + 5 ];
int main( ) {
    scanf("%d",&n);
    scanf("%s", str + 1 ); reverse( str + 1 , str + n + 1 );
    for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]); reverse( a + 1 , a + n + 1 );
    SAM.Build( n , str );

    memset( Ans2 , 0xcf , sizeof( Ans2 ) );
    SAM.Solve();
    for( int i = n - 2 ; i >= 0 ; i -- ) Ans2[ i ] = max( Ans2[ i ] , Ans2[ i + 1 ] );
    for( int i = 0 ; i < n ; i ++ ) {
        if( i != 0 ) Ans1[ i ] += Ans1[ i - 1 ];
        printf("%lld %lld\n", i == 0 ? 1ll * n * ( n - 1 ) / 2 : Ans1[ i ] , Ans2[ i ] == 0xcfcfcfcfcfcfcfcf ? 0 : Ans2[ i ] );
    }
    return 0;
}